Flash memory technology is an electrically rewritable nonvolatile digital memory medium. Being non-volatile, it does not require a sustained voltage to retain digital data within its memory. A flash memory cell typically stores charge on a floating gate to represent a first logic state in the binary state system, while the lack of stored charge represents a second logic state in the binary state system. Flash memory cells typically support a write operation, a read operation, and an erase operation. Like traditional rotating storage media, flash memory is non-volatile. Because of this, data stored in it is retained when power is cut off. This makes it particularly useful for a number of applications such as digital photography, where a full piece of digital “film” may be removed from a camera and replaced with a fresh piece. Removing a flash type digital memory system from a host camera will not result in memory loss.
As flash memory technology has evolved, opportunities in a variety of applications have become possible. In particular, flash memory implementations that emulate the mass storage function of conventional rotating magnetic media, e.g., a hard disk drive or a floppy disk drive, coupled to a host computer system or other host digital system have gained wide acceptance. Hard disk drives and floppy disk drives suffer several deficiencies which are not shared by flash memory technology. First, hard disk drives and floppy disk drives have many moving parts, e.g. an electrical motor, a spindle shaft, a read/write head, and a magnetizable rotating disk. These components give rise to reliability problems and magnify the hard disk drive's and floppy disk drive's susceptibility to failure resulting from the vibration and shock of being dropped or bumped. Secondly, a motor driven disk drive consumes a significant amount of power, substantially shortening the operational time between battery chargings. Finally, accessing data stored in the hard disk drive or the floppy disk is a relatively slow process.
In contrast, a flash memory system possesses many advantages over rotating storage disks. The typical flash memory system has no moving parts, accounting for the higher reliability of the typical flash memory system. In addition, the rugged design of the typical flash memory system withstands environmental conditions and physical mishandling that would otherwise be catastrophic to the hard disk drive or the floppy disk drive. Generally, a user can access data stored in the typical flash memory system fairly quickly. Finally, the power consumption of the typical flash memory system is considerably lower than the hard disk drive's and the floppy disk drive's power consumption.
Because of the market saturation and universal application of rotating media such as hard disk drives, any process or device seeking to supplant disk type memory in the market place must be compatible with existing software and operating systems. Although flash memory technology is well suited for mass storage applications, prior art Flash Memory architecture displays both advantages and disadvantages over legacy data storage devices such as hard disk drives or floppy disks. One of the disadvantages commonly found in Flash Memory devices and systems is their inability to replicate data addressing, storage and retrieval procedures implemented by the hard disk drive and the floppy disk drive. Because market compatibility is essential, an apparatus or process for replicating these processes and achieving compatibility with existing operating systems must typically be built into a flash memory system itself. One means of achieving compatibility in the prior art has been to divide flash memory into sectors which are, in size and architecture, similar in storage capacity and architecture to a sector of a traditional hard drive, as will be discussed in greater detail herein.
Another limitation of flash memory technology is the inability to perform a write operation to a sector of a flash memory cell currently storing data. Unlike a disk drive, which typically just writes over a previous storage area, a sector of a flash memory cell must be erased before data storage can occur. This erase requirement interposes a delay between successive write operations on the same sector.
Additionally, a hard disk can erase and rewrite the same sector a virtually unlimited number of times without degrading system performance. In contrast, every time a write and erase cycle occurs to a sector of a flash memory system, the sector's operability is degraded. Voltage levels required to erase a sector of a flash memory cell typically degrade the insulative layer protecting the floating gate. As a result of cumulative erase operations, the insulation will eventually fail, dislodging bound electrons on the floating gate. When the floating gate can no longer effectively retain charge, the flash memory, or some specific sector within a flash memory cell, becomes inoperable. Sophisticated erasure programs can ameliorate the degradation experienced by the erase operation, but have not yet eliminated deleterious effect altogether. Moreover, the loading and running of sophisticated erasure programs is time consuming, adding to the delay that the erase operation itself creates. Failure to employ protective erase programs only accelerates the degradation resulting from erasure, substantially shortening the useful life of a flash memory cell.
Because of this wearing-out property, which makes the typical flash memory cell unusable after a finite number of erase-write cycles, the data storage procedure implemented by the typical flash memory system must address cumulative gate degradation in an attempt to extend the life of a flash memory cell. One way to slow the degradation of a flash memory cell is to reduce the frequency of repeated write and erase operations to the same sector. This has typically been achieved through wear-leveling programs that attempt to regulate sector usage such that different regions of a flash memory cell are erased an equal number of times, thereby wearing-out at a fairly consistent rate. An additional advantage of cycling data storage through successive sectors in a flash memory is the ability to postpone the erasure of a previous sector until an opportune time, thereby avoiding untimely delays that might otherwise attend the erase process.
Therefore, while the data storage procedure implemented by the typical flash memory system represents an improvement over hard and floppy disk storage in terms of moving parts and power consumption, it suffers potential liabilities which must be overcome.
FIG. 1 illustrates an architecture of a flash memory cell according to the prior art. A flash memory array 100 functions as a nonvolatile mass memory component of the typical flash memory device. The flash memory array 100 is divided into a plurality of data blocks 102, . . . , 106 for storing User and Overhead Data. The data blocks 102, . . . , 106 are conventionally labeled from zero to M−1, where M is the total number of data blocks 102, . . . , 106. Usually, each data block 102, . . . , 106 is selectively programmable and erasable. Each data block 102, . . . 106 is comprised of a plurality of sectors, which will typically emulate a sector of a rotating storage disk, both in terms of capacity, and in terms of many architectural features. Typically, there are sixteen sectors, e.g. 112, . . . , 116 numbered from zero through fifteen, in each data block 102, 104, etc. Because the number of sectors may vary, however, FIG. 1 represents each data block 102, . . . , 106 as comprising N sectors, respectively numbered zero through N−1.
Each data block 102, . . . , 106 is defined by a unique Virtual Physical Block Address (VPBA). Assuming for exemplary purposes only that the number of sectors in a physical data block is sixteen, numbered from zero through fifteen, a sector is defined by a Physical Block Address (PBA) comprised of the VPBA of the data block, and the sector number. For example, assume data block 106 were defined according to the Virtual Physical Block Address (VPBA) 1024. Sector fifteen would be defined by the Physical Block Address (PBA) 1024:15.
FIG. 2 illustrates the features of an individual sector 200 according to the prior art. The sector 200 is exemplary of the individual sectors 112, . . . 136 depicted in FIG. 1. A prior art sector 200 typically includes a Data Field 202 for storing User Data, and an Extension Field 204 for storing Overhead Data. Because the Data Field and the Extension Field are part of the same sector according to the prior art, a significant limitation of the prior art has been the inability to erase User Data and Overhead Data independently. Architectural limitations prohibit targeted erasures below the sector level. Accordingly, sub-portions of a sector, such as a Data Field 202 or Extension Field 204 cannot be erased independently.
As noted in conjunction with FIG. 2, the Data Field 202 is typically five hundred twelve bytes, which corresponds with a storage sector length in a commercially available hard disk drive or floppy disk drive. The Extension Field 204 is typically sixteen bytes total, and is comprised of plurality of fields or registers 206, . . . , 212 of varying sizes which contain overhead data. By having both a User Data Field 202 and an Extension Field 204, a Sector 200 of Flash Memory is equipped to emulate a sector of data storage area typically found on a rotating storage media such as a disk drive. A recognized Error Correction Code (ECC) is used to generate ECC data stored within the ECC Field 206. The ECC data within a particular ECC field 206 is used for error checking with respect to the User Data stored within the corresponding Data Field 202 of the same sector. The ECC Field 206 is typically four bytes. An LBA Field 208 is used for storing a Logical Block Address (LBA) or Virtual Logical Block Address (VLBA) associated with data stored in the Data Field 210, and is typically 2 bytes of memory, for correlative purposes, as will be discussed in greater detail herein. A Flag Field 210 is used to store a plurality of flags indicating if a block is defective, if a block is used or unused, and if the data stored in a block is current or obsolete. A flag field is typically one byte. A field of optional spare overhead bits 212 typically comprises the unused memory area within the extension field 204.
FIG. 3 illustrates a data storage process within a flash memory system according to the prior art. A host digital system sends User Data 300 defined according to Virtual Logical Block Address seventeen to a flash memory system for storage. The Virtual Logical Block Address is typically assigned by the host. A Virtual Logical Block of User Data 300 is divided up into component logical blocks of data 310, . . . , 316, each comprising distinct addresses 302, . . . , 308. Each logical block 310, . . . , 316 typically holds an amount of User Data equivalent to the memory capacity of the User Data area 202 of a sector 200 of flash memory, that is, five hundred twelve bytes. As previously noted, individual sectors 112, . . . , 136 are defined by unique Physical Block Addresses (PBA's).
The amount of memory in a sector defined by a Physical Block Address (PBA) is equivalent to the amount of User Data in a logical block defined by an LBA. A Virtual Logical Block 300 is comprised of multiple Logical Blocks 310, . . . , 316. Ideally, the number of Logical Blocks of data 310, . . . , 316 making up a Virtual Logical Block 300 are equivalent to the number of sectors 322, . . . , 328 making up a data block 320. Accordingly, a Physical Block of memory defined by a Virtual Physical Block Address (VPBA) represents an amount of memory equivalent to the amount of data represented by a Virtual Logical Block Address (VLBA) of User Data. One Virtual Logical Block of incoming User Data 300 defined according to a Virtual Logical Block Address, depicted here as address seventeen, is therefore advantageously stored in one Physical Block of flash memory defined according to a Virtual Physical Block Address, depicted here as address one hundred thirty-four.
The reason for storing logical data of one address into physical memory of a different address stems from the difference between flash memory systems and traditional disk-type memories. In a conventional rotating magnetic media, the LBA-to-PBA correlation is static because updated versions of the data are programmed over old versions of the data. It is recalled however that repeated writing and erasing degrades the life of a flash memory, and that wear-leveling programs are typically employed to ensure a substantially even utilization of all physical data storage areas within a flash memory. It will be recalled that a management algorithm typically attempts to cycle through all Physical Data Blocks before returning to the original Physical Data Block, thereby producing an even rate of use or wear among Physical Data Blocks. In contrast, a logical address may be updated or reused without cycling through all other VLBA's first. Accordingly, incoming data defined by a reused Logical Block Address will not typically be stored in the same physical Sector that previously stored the data defined by that LBA. A distinctive characteristic of the data storage algorithm implemented by the typical flash memory system, therefore, lies in the continuously changing relation between the LBA's and the PBA's.
The Virtual Logical Block of data 300 comprised of a collection of Logical Blocks of data 310, . . . , 316 is defined by a common VLBA, in this case “seventeen,” and a succession of consecutive Logical Block offsets, numbered zero through fifteen. The Logical Block Addresses are therefore numbered from “17:0” 302 through “17:15” 308. Consecutive sectors 322, . . . , 328 within a Data Block are similarly distinguished by PBA offset, typically numbered zero through fifteen, and a common VPBA, in this case, “one hundred thirty four.” The VPBA plus the PBA offset define a unique PBA or Physical Block Address 310, . . . , 316 for each sector. As noted, each Logical Block 310, . . . , 316 represents an amount of data equivalent to a physical Sector 322, . . . , 328.
A 64 meg memory typically comprising 1024 Physical Data Blocks 102, . . . 106 of memory capacity could therefore store 1024 VLB's of data. One thousand twenty four Physical Data Blocks would be defined according to one thousand twenty four Virtual Physical Block Addresses, and one thousand twenty four Virtual Logical Blocks would be defined by one thousand twenty four Virtual Logical Block Addresses. A ten bit register is required to define one thousand twenty four possible addresses. In a 64 meg flash memory system, therefore, a minimum of ten bits are dedicated to defining a Virtual Logical Block Address or a Virtual Physical Block Address. Accordingly, an LBA Field such as the Temporary LBA Register 340 (FIG. 3) can be conceptually divided into two registers, an upper register or VLBA Field 342 and a lower register or LBA Offset Field, 344. The entire Temporary LBA Register 340 is typically two bytes in length, though it could be greater if necessary. As noted, at least ten bits must be dedicated to the VLBA register 342, and at least four bits to the LBA offset register 344. In a two-byte (sixteen bit) register, the remaining two bits may be located according to the architectural preference of the computer engineer.
Because of the constantly changing relationship between LBA's and PBA's, rapid data retrieval is typically aided by a Space Manager 400, as seen in FIG. 4. A space manager 400 typically comprises a volatile RAM memory for maintaining a correlation between a logical block addresses (LBA's) of data and the physical block addresses (PBA's) of the sectors which store the most recent update of a logical block of data. This correlation enables the Host to subsequently retrieve the data according to its Logical Block Address. A preestablished set of VLBA's 460, . . . , 468 available for association with incoming data are consecutively assigned to a series of Correlation Fields 450, . . . , 458. Each Correlation Field includes a PBA Register 408, which is comprised of VPBA register 410 for storing an address of a Physical Data Block and a PBA offset 412. As with the LBA register discussed earlier, the PBA register typically comprises two bytes. Ten bits are required for a 64 meg flash system with 1024 data blocks. Since a data block typically comprises sixteen sectors, four bits are typically required for the PBA offset 412. The remaining two bits making up a two-byte PBA field 408 may be located in either field, or used as architectural concerns allow. In FIG. 1 the total number of physical data blocks in a flash memory was noted to be M, respectively numbered zero through M minus one. FIG. 4 similarly illustrates that there are “M” consecutive logical addresses 460, . . . , 468, also numbered zero through M minus one, corresponding to a plurality of Correlation Fields 450, . . . 458 used for storing Virtual Physical Block Addresses. Accordingly, the number of potential VLBA's 460, . . . , 468 within a Space Manager 400 matches the potential number of Physical Block Addresses within a flash memory cell. It is therefore noted that Space Managers 400 typically correlates physical and logical addresses only down to the Physical Data Block level. This is primarily because space managers consume valuable memory, and correlation to a finer level of memory would consume more memory.
As noted, a space manager 400 is typically implemented as a volatile RAM array. Typically, the space manager 400 comprises SRAM cells. However, DRAM cells can be substituted for the SRAM cells. Because of the speed of accessing information stored in an SRAM or DRAM medium, a Space Manager 400 provides rapid correlation data between Logical Block Addresses and Physical Block Addresses.
Each volatile Correlation Field 450, . . . , 458 includes a plurality of Flags, including a Defective Block Flag 420, an Obsolete Data Flag 430, and an Used Block Flag 440. Each Flag 420, 430, 440 typically comprises a single bit capable of depicting a first and second binary state. When a Defective Block Flag 420 is set from a first value to a second value, the flag indicates that the Physical Data Block is defective. A Physical Data Block marked as defective will be passed over for future data storage. When the Used Block Flag 440 is set, it indicates that data is currently stored in the physical address signified by the VPBA stored in the associated VPBA register. If data is stored, it must either be current or obsolete, typically indicated by a first or second binary state respectively of the Obsolete Data Flag 430. The erase operation is normally be used only when data has been obsoleted. If data defined by a Virtual Logical Block Address is updated, the fresh data is stored in a new physical block 102, . . . 106, and the new VPBA is stored in the VPBA register 410 of the proper correlation field 450, . . . , 458. Consecutive sectors in a data block are typically filled one sector at a time in a continuous data storage operation. If a VLB is only partly comprised of data, for example, eight of the sixteen logical blocks containing actual User Data, the controller will nevertheless typically go through the motions of loading all sixteen logical blocks of a VLB into the data area 202 (FIG. 2) of sixteen consecutive sectors of a physical block. If an update of a single logical block within that Virtual Logical Block is subsequently received, it cannot be stored in the original PBA. A new physical block must be selected. No new incoming data will be stored in a Physical Data Block flagged as “used.” When the Obsolete Data Flag 430 is set to a second binary state, the data stored in the corresponding physical block is marked as obsolete, and the Physical Data Block is targeted for erasure. Incoming data may then be reassigned to the physical data block.
In practice, when the logical address and associated data are received for the first time, the typical flash memory system utilizes the space manager 400 to search for the data block with an un-set Defective Block Flag 420 and an un-set Used Block Flag 440 for storing the data. After storing the data therein, the Used Block Flag 440 and an equivalent flag in the Flag Field 240 (FIG. 2) are set to a second binary value, indicating that the Physical Data Block is now used for storing data.
A host presents data defined by an LBA or series of LBA's for storage within the flash memory system. The data is stored in a corresponding sector or series of sectors defined according to a PBA or series of PBA's. When the host requests the data for retrieval, the request is again in the form of a logical address. The data is retrieved from a physical local bearing a physical address through a correlation register such as found in the space manager. The storage and retrieval of data through the operation of the space manager 400 is performed through a series of concatenations and masking operations described in the flow chart of FIG. 5. Additionally, the space manager 400 assists the typical flash memory system in executing the erase operation. Some prior art flash memories can perform the erase operation in the background while another operation is being performed. Alternatively, the erase operation can be postponed until all other operations within a flash memory have ceased. Before initiating the erase operation, the typical flash memory system uses the space manager 400 to search for the data blocks having a set Obsolete Data Flag 430 and an un-set Defective Block Flag 420. These data blocks are then targeted for erasure.
Although correlation between logical and physical memory must be maintained, RAM space managers 400 consume valuable memory. One way of minimizing the memory consumption resulting from the presence of a RAM space manager 400 is to limit correlation to larger groups of data, such as correlating Virtual Logical Blocks Addresses to Virtual Physical Block Addresses defining large blocks of physical memory, thereby resulting in fewer correlation registers within the space manager 400. Returning to FIG. 3, if data from sixteen consecutive logical blocks 310, . . . 316 of User Data defined according to sixteen consecutive LBA's 302, . . . , 308 were stored in sixteen physical sectors 322, . . . , 328 defined according to sixteen consecutive PBA's 310, . . . , 316, a default correlation would exist between the lower order address by virtue of the storage arrangement. Through use of such an arrangement, the space manager 400 need only correlate VLBA's to VPBA's, thereby reducing the space manager 400 to 1/16th the size according to an embodiment comprising sixteen sectors per data block.
FIG. 5 is a flow chart describing the data storage process. The process is described in conjunction with the data fields and registers of FIG. 3. In the first step 502, Virtual Logical Block seventeen 300 of User Data (FIG. 3) is received from a Host for storage in a non-volatile Flash Memory Unit. In step 504, the controller moves the first LBA of the new file of User Data 300 into the Temporary LBA Register 340, which is typically a two bit register in 65 meg flash systems. In step 506 the controller selects an unused, non-defective data block for storage, and writes the VPBA of that data block into the VPBA register 352 of the Temporary PBA Register 351. In step 508, the controller masks the higher order bits (the VLBA) 342 of the Temporary LBA Register 340 and concatenates the lower order bits 344 designated as the “sector offset” into the PBA sector offset 354. In step 510, the controller stores the logical block of data 310, . . . , 316 defined by the address in the Temporary LBA Register 340 in the physical sector defined by the address in the PBA Temporary Register 351. In step 512, the controller writes the value found in the VPBA Temporary Register (352) into the correlation register 450, . . . 458 corresponding to the VLBA 460, . . . , 468 found in the Temporary VLBA Register 342.
FIG. 6 discloses a similar process for retrieving data from the flash memory system at the request of the host. According to step 602, the host requests data defined by an LBA. In step 604, the LBA of the request is written in the Temporary LBA Register 340. In step 606, the lower order bits within the LBA Offset 344 are masked, and the higher order bits defining the VLBA 342 are moved into the Temporary VLBA Register 360. In step 608, through the use of the space manager 400, the controller locates the correlation register 450, . . . , 458 corresponding to the address in the temporary VLBA Register 360. In step 610 the controller moves the VPBA 410 of the select correlation register into the upper register 352 of the PBA Temporary Register 351. In step 612 the controller concatenates the LBA sector offset 344 into the PBA sector offset 354. In step 614, the controller retrieves data found in the sector defined according to the address in the PBA Temporary Register 351. In step 616, the controller sends the retrieved data to the host, and defines the data according to the logical address found in the Temporary LBA Register 340.
The sequence of steps described in FIGS. 5 and 6 is intended to illustrate a means of correlating logical and physical addresses to perform data storage and retrieval according to the prior art. Because the specific mechanics of storage could be performed in a number of equivalent ways, the process disclosed in FIGS. 5 and 6 are not intended to represent these specific processes as the only means of data storage and retrieval according to the prior art, nor to limit data storage and retrieval in the present invention. The details are disclosed simply to illustrate one way of performing a data storage process in a manner that preserves a natural correlation between LBA's and PBA's. According to the process as described above, the LBA offset 344 is used as a PBA offset 354 when storing a VLB of data into a Physical Sector.
Due to the volatile nature of the space manager 400, loss of power erases the data stored in a volatile RAM such as that used in the typical Space Manager. However, any data stored in the Space Manager is backed up in the non-volatile memory, typically in the Extension Fields 204 of the various sectors 112, . . . , 136 of the Flash Memory cells. Power loss has no damaging effect on memory stored in non-volatile storage mediums.
Because loss of power typically destroys the contents of a RAM memory, overhead data is typically be loaded from the Extension Field 204 of select sectors into the Space Manager 400 at power up, or upon a reset command. A VLBA 360 stored in the LBA register 208 of an Extension Field 204 establishes a non-volatile correlation between the Virtual Physical Block Address (VPBA) 364 of the sector 322 in which the Extension Field 204 resides, and the Virtual Logical Block Address (VLBA) 360 stored in the LBA register 208. The Flags within the Flag Registers 420, 430, 440 are also typically loaded from the non-volatile memory field 210 (FIG. 2) into the Space Manager 400 during start up, or upon a reset command.
To control the operations of the typical flash memory system, the typical flash memory system further comprises a controller (not shown) coupled to the flash memory device. Since the space manager 400 is an integral part of the operations performed by the typical flash memory system, the space manager 400 is typically designed within the controller, thereby improving system performance. The silicon area necessary for a large addressable storage capacity, however, typically makes it economically unfeasible to form both the controller and the actual flash memory device on the same integrated circuit. As a result, the controller and flash memory device are typically formed on separate integrated circuits. By forming the controller and the flash memory on separate integrated circuits, manufacturing processes can be employed which are more ideally suited for the formation of each of these individual components, more easily satisfying specific parameters and operating requirements.
Although the space manager 400 enables the typical flash memory system to achieve superior performance, this superior performance is attained at a significant cost in silicon area on the integrated circuit on which the controller is formed. Assuming, for exemplary purposes only, a 64 MegaBit, flash memory system with 1024 data blocks and sixteen sectors per data block, the exemplary flash memory system would be comprised of 16,384 sectors. As previously noted, if a single VLB 300 is stored in a single data block 320, only 1024 Correlation Fields 450, . . . 458 are needed within the space manager 400. If a single VLB 300 of data were fragmented among multiple data blocks, the space manager 400 would need 16,384 Correlation Fields 450, . . . 458 to keep correlate all the logical and physical addresses.
As previously noted, multiple liabilities inhere from storing overhead data such as error correction data 206 and flags 210 in the same sector 200 as user data 202. On power up, a lengthy and comprehensive evaluation, potentially accessing every sector of the flash memory must be performed to update the space manager. This process is both time consuming and complex. Segregating overhead data into a hand full of data blocks can substantially improve the speed and efficiency with which the space manager is loaded on power up. A second problem stemming from the mixing of User Data and Overhead Data in the same sector deals with gate degradation. As earlier noted, repeated write and erase cycles eventually “wear-out” a flash memory system. When Overhead Data and User Data are in the same sector, they are exposed to an equal number of write/erase cycles. In the prior art, therefore, the error correction data 206 in a given sector 200 is likely to become degraded at the same rate the user data 202 within that sector. Relying on degraded error correction field to monitor and possibly correct User Data is problematic at best. Finally, when overhead data and user data are stored in the same sector, it was not possible to independently program or erase the overhead data were user data. There exists therefore a need for segregating user data and overhead data into independently addressable, programmable and erasable data blocks within a flash memory cell.
There further exists the need for segregating user data from overhead data in a way that utilizes memory in an efficient manner when one Logical Block Addresses repeated more often than other Logical Block Addresses. There further exists a need for segregating overhead data from user data in a way that makes efficient use of memory when Logical Block Addresses are used at an equal rate. There further exists a need for segregating overhead data from user data in a way that makes efficient use of memory when the comparative usage of various Logical Block Addresses is variable or unknown.